\begin{thesisabstract}

When building storage systems that aim to simultaneously provide robustness,
scalability, and efficiency, one faces a fundamental tension, as higher robustness
typically incurs higher costs and thus hurts both efficiency and scalability.
My research shows that an approach to storage system design based on a simple
principle---separating data from metadata---can yield systems that address
elegantly and effectively that tension in a variety of settings. One observation
motivates our approach: much of the cost paid by many strong protection
techniques is incurred to detect errors. This observation suggests an
opportunity: if we can build a low-cost oracle to detect errors and
identify correct data, it may be possible to reduce the cost of protection without
weakening its guarantees. This dissertation shows that metadata, if carefully
designed, can serve as such an oracle and help a storage system protect
its data with minimal cost.

This dissertation shows how to effectively apply this idea in three very different systems:
Gnothi---a storage replication protocol that combines the high availability of asynchronous
replication and the low cost of synchronous replication for a small-scale block storage;
Salus---a large-scale block storage with unprecedented guarantees in terms of consistency,
availability, and durability in the face of a wide range of server failures; and Exalt---a
tool to emulate a large storage system with 100 times fewer machines.

\end{thesisabstract}

